翻訳と辞書 Words near each other ・ Chiemi ・ Chiemi Chiba ・ Chiemi Eri ・ Chiemi Takahashi ・ Chieming ・ Chiemsee ・ Chiemsee (municipality) ・ Chiemsee Cauldron ・ Chien Chung-liang ・ Chien de Jean de Nivelle ・ Chien Français Blanc et Noir ・ Chien Français Blanc et Orange ・ Chien Français Tricolore ・ Chien Hsin University of Science and Technology ・ Chien Kok-Ching ・ Chien search ・ Chien Shih-Liang ・ Chien Tai-lang ・ Chien Tang River Bridge ・ Chien Wei-chuan ・ Chien Wei-zang ・ Chien Wen-pin ・ Chien Yu-chin ・ Chien Yu-hsiu ・ Chien-Cheng Circle ・ Chien-Chi Chang ・ Chien-gris ・ Chien-Ming Wang ・ Chien-Shiung Wu ・ Chien-Shiung Wu College Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Chien search ： ウィキペディア英語版 Chien search In abstract algebra, the Chien search, named after Robert T. Chien, is a fast algorithm for determining roots of polynomials defined over a finite field. The most typical use of the Chien search is in finding the roots of error-locator polynomials encountered in decoding Reed-Solomon codes and BCH codes. ==Algorithm== We denote the polynomial (over the finite field GF($q$)) whose roots we wish to determine as: :$\backslash \; \backslash Lambda(x)\; =\; \backslash lambda\_0\; +\; \backslash lambda\_1\; x\; +\; \backslash lambda\_2\; x^2\; +\; \backslash cdots\; +\; \backslash lambda\_t\; x^t$ Conceptually, we may evaluate $\backslash Lambda(\backslash beta)$ for each non-zero $\backslash beta$ in GF($q$). Those resulting in 0 are roots of the polynomial. The Chien search is based on two observations: * Each non-zero $\backslash beta$ may be expressed as $\backslash alpha^$ for some $i\_\backslash beta$, where $\backslash alpha$ is a primitive element of $\backslash mathrm(q)$, $i\_\backslash beta$ is the power number of primitive element $\backslash alpha$. Thus the powers $\backslash alpha^i$ for cover the entire field (excluding the zero element). * The following relationship exists: :$$ \begin \Lambda(\alpha^i) &=& \lambda_0 &+& \lambda_1 (\alpha^i) &+& \lambda_2 (\alpha^i)^2 &+& \cdots &+& \lambda_t (\alpha^i)^t \\ &\triangleq& \gamma_ &+& \gamma_ &+& \gamma_ &+& \cdots &+& \gamma_ \end :$$ \begin \Lambda(\alpha^) &=& \lambda_0 &+& \lambda_1 (\alpha^) &+& \lambda_2 (\alpha^)^2 &+& \cdots &+& \lambda_t (\alpha^)^t \\ &=& \lambda_0 &+& \lambda_1 (\alpha^i)\,\alpha &+& \lambda_2 (\alpha^i)^2\,\alpha^2 &+& \cdots &+& \lambda_t (\alpha^i)^t\,\alpha^t \\ &=& \gamma_ &+& \gamma_\,\alpha &+& \gamma_\,\alpha^2 &+& \cdots &+& \gamma_\,\alpha^t \\ &\triangleq& \gamma_ &+& \gamma_ &+& \gamma_ &+& \cdots &+& \gamma_ \end In other words, we may define each $\backslash Lambda(\backslash alpha^i)$ as the sum of a set of terms $\backslash$, from which the next set of coefficients may be derived thus: :$\backslash \; \backslash gamma\_\; =\; \backslash gamma\_\backslash ,\backslash alpha^j$ In this way, we may start at $i\; =\; 0$ with $\backslash gamma\_\; =\; \backslash lambda\_j$, and iterate through each value of $i$ up to $(q-1)$. If at any stage the resultant summation is zero, i.e. :$\backslash \; \backslash sum\_^t\; \backslash gamma\_\; =\; 0,$ then $\backslash Lambda(\backslash alpha^i)\; =\; 0$ also, so $\backslash alpha\_i$ is a root. In this way, we check every element in the field. When implemented in hardware, this approach significantly reduces the complexity, as all multiplications consist of one variable and one constant, rather than two variables as in the brute-force approach. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chien search」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.